#include<stdio.h>
#include<stdlib.h>
struct node
{
int value;
struct node *next;
};
void insert(struct node **,int);
void display(struct node *);
void inspos(struct node **,int,int);
int length(struct node *);
int count(struct node *,int);
int index(struct node *,int);
void reverse(struct node **);
void pop(struct node **,int);
void remuv(struct node **,int);
void extend(struct node **,struct node **);
void sorts(struct node **);
void main()
{
struct node *p;
int num,m,x,i;
int ch;
p=NULL;
printf("Enter the number of elements in list");
scanf("%d",&x);
for(i=0;i<x;i++)
{
printf("Enter number");
scanf("%d",&num);
insert(&p,num);
}
display(p);
while(ch!=0)
{
printf("ENTER FUNCTION NO.\n 1. Insert \n 2. Append \n 3. Length \n 4. Count \n 5. Index \n 6. Reverse \n 7. Pop \n 8. Remove \n 9. Extend \n 10. Sort \n");
scanf("%d",&m);
switch(m)
{
case 1:
{ int num1,pos;
printf("Enter position no. (starts from 1) or negative index(position)");
scanf("%d",&pos);
printf("Enter element to be insert "); 
scanf("%d",&num1);
if(pos<0)
pos=length(p)+1+pos;
inspos(&p,num1,pos);
display(p);
break;
}
case 2:
{int num2;
printf("Enter element to be append "); 
scanf("%d",&num2);
insert(&p,num2);
display(p);
break;}
case 3:
{
printf("Length of list is %d \n",(length(p)));
break;
}
case 4:
{int l;
printf("Enter no ");
scanf("%d",&l);
printf("\n No. of given no are %d \n",(count(p,l)));
break;}
case 5:
{
int l;
printf("Enter no ");
scanf("%d",&l);
printf("\n Index of given no. %d \n",(index(p,l)));
break;
}
case 6:
{
reverse(&p);
display(p);
break;
}
case 7:
{int k;
printf("Enter position to be pop (starts from 1) or negative index(position) \n" );
scanf("%d",&k);
if(k<0)
k=length(p)+1+k;
pop(&p,k);
display(p);
break;
}
case 8:
{
int k;
printf("Enter element to delete \n");
scanf("%d",&k);
remuv(&p,k);
display(p);
break;
}
case 9:
{int k,j,no;
struct node *q;
q=NULL;
printf("Enter the number of elements in list to be extend");
scanf("%d",&k);
for(j=0;j<k;j++)
{
printf("Enter number");
scanf("%d",&no);
insert(&q,no);}
display(q);
extend(&p,&q);
display(p);
break;
}
case 10:
{
sorts(&p);
display(p);
break;
}

}
printf("Enter 0 to exit or 1 to do more operations \n");
scanf("%d",&ch);
}
}

void insert(struct node **ptr,int num)
{
struct node *t,*s;
t=malloc(sizeof(struct node));
t->value=num;
t->next=NULL;
if(*ptr==NULL)
{
*ptr=t;
}
else
{
t=*ptr;
while(t->next!=NULL)
{
t=t->next;
}
s=malloc(sizeof(struct node));
s->value=num;
s->next=NULL;
t->next=s;
}
}

void display(struct node *ptr1)
{ printf("[");
while(ptr1!=NULL)
{
printf(" %d ",ptr1->value);
if((ptr1->next)!=NULL)
printf(",");
ptr1=ptr1->next;
}
printf("] \n");
}

void inspos(struct node **ptr1,int num2,int pos)
{
int i;
struct node *temp,*t,*r;
temp=(struct node *)malloc(sizeof(struct node));
temp->value=num2;
r=*ptr1;       
if (pos == 1)
{
if ( *ptr1== NULL)
{
*ptr1=temp;
(*ptr1)->next=NULL;
}
else
{
temp->next=*ptr1;
*ptr1=temp;
}
}
else
{
for(i=1;i<pos;i++)
{
t=r;   
r=r->next;
}
t->next=temp;
t=temp;
t->next=r;
}
}

int length(struct node* ptr2)
{
int c=0;
while(ptr2!=NULL)
{
ptr2=ptr2->next;
c++;
}
return c;
}

int count(struct node* ptr2,int k)
{
int c=0;
while(ptr2!=NULL)
{
if((ptr2->value)==k)
c++;
ptr2=ptr2->next;
}
return c;
}

int index(struct node* ptr2,int k)
{
int c=-1,m;
m=c;
while(ptr2!=NULL)
{
if((ptr2->value)==k)
{
if(c<0)
c=0;
break;}
ptr2=ptr2->next;
c++;
if(c==0)
c=1;
}
return c;
}

void reverse(struct node **q)
{
struct node *m, *n,*s;
m=*q;
n=NULL;
while(m!=NULL)
{
s=n;
n=m;
m=m->next;
n->next=s;
}
*q=n;
}

void pop(struct node **p,int k)
{
    struct node *temp, *m, *n;
int c=0,num;
temp=*p;
n=*p;
for(c=0;c<k;c++)
{
if(c+1==k)
{num=n->value;
printf("Number is %d ",num);}
n=n->next;
}

while(temp!=NULL)
{
if(temp->value==num)
{
if(temp==*p)
{
*p=temp->next;
free(temp);
return;
}
else
{
m->next=temp->next;
free(temp);
return;
}
}
else
{
m=temp;
temp=temp->next;
}
}
}

void remuv(struct node **ptr7,int num)
{
struct node *temp, *m;
temp=*ptr7;
while(temp!=NULL)
{
if(temp->value==num)
{
if(temp==*ptr7)
{
*ptr7=temp->next;
free(temp);
return;
}
else
{
m->next=temp->next;
free(temp);
return;
}
}
else
{
m=temp;
temp= temp->next;
}

}
printf("ERROR- ELEMENT %d NOT FOUND", num);
}

void extend(struct node **ptr8,struct node **ptr9)
{int n;
struct node *t,*m;
t=*ptr9;
m=*ptr8;
while(t!=NULL)
{n=t->value;
insert(&m,n);
t=t->next;
}
}

void sorts(struct node **ptr0)
{
struct node *i, *j, *l, *h;
int tmp,flag,k;
h=*ptr0;
i=h;
while((i->next)!=0)
{
k=i->value;
j=i->next;
while(j!=NULL)
{
if((j->value)<k)
{
l=j;
k=j->value;
flag=1;
}
j=j->next;
}
if(flag==1)
{
tmp=i->value;
i->value=k;
l->value=tmp;
}
flag=0;
i=i->next;
}
}

